n, m = list(map(int,input().split()))
myList = []
for _ in range(n):
myList.append(list(map(int,input().split())))
mySumCom = 0
mySumUnCom = 0
mySubList = []
for i in myList:
mySumCom += i[1]
mySumUnCom += i[0]
mySubList.append(i[0]-i[1])
if mySumCom > m:
print(-1)
exit()
else:
mySub = mySumUnCom - m
mySum = 0
if m >= mySumUnCom:
print(0)
exit()
mySubList.sort(reverse = True)
for i,v in enumerate(mySubList):
mySum += v
if mySum >= mySub:
print(i+1)
exit()
#include <stdio.h>
typedef long long ll;
struct disk{
ll ori;
ll comp;
};
void merge(disk arr[], int kiri, int tengah, int kanan){
int a = tengah - kiri + 1;
int b = kanan - tengah;
disk k1[a], k2[b];
for (int i = 0; i < a; i++){
k1[i] = arr[kiri + i];
}
for (int j = 0; j < b; j++){
k2[j] = arr[tengah + 1 + j];
}
int l = 0, m = 0, n = kiri;
while (l < a && m < b){
if (k1[l].ori - k1[l].comp >= k2[m].ori - k2[m].comp){
arr[n] = k1[l];
l++;
} else {
arr[n] = k2[m];
m++;
}
n++;
}
while (l < a){
arr[n] = k1[l];
l++;
n++;
}
while (m < b){
arr[n] = k2[m];
m++;
n++;
}
}
void mergeSort(disk arr[], int kiri, int kanan){
if (kiri < kanan){
int tengah = kiri + (kanan - kiri) / 2;
mergeSort(arr, kiri, tengah);
mergeSort(arr, tengah + 1, kanan);
merge(arr, kiri, tengah, kanan);
}
}
int main(){
int n;
ll size;
ll sum = 0;
scanf("%d %lld", &n, &size);
disk ivan[n];
for (int i = 0; i < n; i++){
scanf("%lld %lld", &ivan[i].ori, &ivan[i].comp);
sum += ivan[i].ori;
}
mergeSort(ivan, 0, n - 1);
int flag = 0;
for (int i = 0; i <= n; i++){
if (sum <= size){
printf("%d", i);
flag = 1;
break;
}
sum -= (ivan[i].ori - ivan[i].comp);
}
if (flag == 0){
printf("-1");
}
}
1234A - Equalize Prices Again | 1613A - Long Comparison |
1624B - Make AP | 660B - Seating On Bus |
405A - Gravity Flip | 499B - Lecture |
709A - Juicer | 1358C - Celex Update |
1466B - Last minute enhancements | 450B - Jzzhu and Sequences |
1582C - Grandma Capa Knits a Scarf | 492A - Vanya and Cubes |
217A - Ice Skating | 270A - Fancy Fence |
181A - Series of Crimes | 1638A - Reverse |
1654C - Alice and the Cake | 369A - Valera and Plates |
1626A - Equidistant Letters | 977D - Divide by three multiply by two |
1654B - Prefix Removals | 1654A - Maximum Cake Tastiness |
1649A - Game | 139A - Petr and Book |
1612A - Distance | 520A - Pangram |
124A - The number of positions | 1041A - Heist |
901A - Hashing Trees | 1283A - Minutes Before the New Year |